package monotonousStack

import (
	"fmt"
	C "gitee.com/ljfirst/algo-go-sdk/common/constant"
	"gitee.com/ljfirst/algo-go-sdk/src/data_structure/heap_stack_queue/stack"
)

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/6/28 19:10
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 单调栈 下一个更大元素
 * 给一个数组，返回一个等长的数组，对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1.
 * 另一道相似题目：https://leetcode-cn.com/problems/daily-temperatures/
 * input:  {2, 1, 2,  4,  3}
 * output: {4, 2, 4, -1, -1}
 * */
type MonotonousStack struct {
}

func (m *MonotonousStack) NextValue(array []int) []int {
	if len(array) < 2 {
		return array
	}
	ans := make([]int, len(array), len(array))
	stacks := &stack.ArrayStack{}
	for i := len(array) - 1; i >= 0; i-- {
		for !stacks.Empty() && array[i] >= stacks.Peak().(int) {
			stacks.Pop()
		}
		if stacks.Empty() {
			ans[i] = -1
		} else {
			ans[i] = stacks.Peak().(int)
		}
		stacks.Push(array[i])
	}
	return ans
}

func (m *MonotonousStack) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{C.MonotonousStack},
		Desc: &C.Desc{
			Name:   "MonotonousStack",
			NameCn: "单调栈:下一个更大元素",
		},
	}
}

func StrDemo() {
	// grammar数组分割 Go语言字符串分割为数组：https://www.php.cn/faq/500024.html
	// grammar数组转asc数组, grammar数组转字符数组
	s := "23456789"
	for i, i2 := range s {
		// | 2 + 50 - 50 | 3 + 51 - 51 | 4 + 52 - 52 | 5 + 53 - 53 | 6 + 54 - 54 | 7 + 55 - 55 | 8 + 56 - 56 | 9 + 57 - 57
		fmt.Print(" | ", string(i2), " + ", i2, " - ", s[i])
	}
	fmt.Println()
	strRune := []rune(s)
	for _, i2 := range strRune {
		// 50 + 51 + 52 + 53 + 54 + 55 + 56 + 57 +
		fmt.Print(i2, " + ")
	}
}
